package Solutions;

/**
 * @Classname FindMedianSortedArrays
 * @Description TODO
 * @Date 2021/3/2 11:07
 * @Created by ASUS
 */
public class FindMedianSortedArrays {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int total = nums1.length + nums2.length + 1;
        int totalLeft = total / 2;
        int left = 0, right = nums1.length;
        while (left < right) {// 二分寻找最佳分隔线
            int Median1 = left + (right - left + 1) / 2;
            int Median2 = totalLeft - Median1;
            if (nums1[Median1 - 1] > nums2[Median2]) {
                // [left, Median1 - 1]
                right = Median1 - 1;
            } else {
                // [Median, right]
                left = Median1;
            }
        }
        int median1 = left + (right - left + 1) / 2;
        int median2 = totalLeft - median1;
        int
                _nums1 = median1 == 0 ? Integer.MIN_VALUE : nums1[median1 - 1],
                nums1_ = median1 == nums1.length ? Integer.MAX_VALUE : nums1[median1],
                _nums2 = median2 == 0 ? Integer.MIN_VALUE : nums2[median2 - 1],
                nums2_ = median2 == nums2.length ? Integer.MAX_VALUE : nums2[median2];
        if ((nums1.length + nums2.length) % 2 == 1) return Math.max(_nums1, _nums2);
        else return (Math.max(_nums1, _nums2) + Math.min(nums1_, nums2_)) / 2.0;
    }

}

